#ifndef STX_BINARY_SEARCH_HPP
#define STX_BINARY_SEARCH_HPP

#include <functional>

namespace stx {

template<typename RandomAccessIterator, typename T>
RandomAccessIterator binary_search(
    RandomAccessIterator begin,
    RandomAccessIterator end,
    const T& value)
{
    RandomAccessIterator retval(end), iter, prev_iter(end), left(begin), right(end);
    std::less<T> cmp;
    for (;;) {
        iter = left + (right - left)/2;
        if (*iter == value) {
            retval = iter;
            break;
        }
        if (iter == prev_iter) {
            break;
        }
        if (cmp(value, *iter)) {
            right = iter;
        } else {
            left = iter;
        }
        prev_iter = iter;
    }
    return retval;
}

} // namespace stx

#endif // STX_BINARY_SEARCH_HPP
